{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Race Car"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: racecar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #赛车"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "你的赛车可以从位置 <code>0</code> 开始，并且速度为 <code>+1</code> ，在一条无限长的数轴上行驶。赛车也可以向负方向行驶。赛车可以按照由加速指令 <code>'A'</code> 和倒车指令 <code>'R'</code> 组成的指令序列自动行驶。\n",
    "<ul>\n",
    "\t<li>当收到指令 <code>'A'</code> 时，赛车这样行驶：\n",
    "\t<ul>\n",
    "\t\t<li><code>position += speed</code></li>\n",
    "\t\t<li><code>speed *= 2</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>当收到指令 <code>'R'</code> 时，赛车这样行驶：\n",
    "\t<ul>\n",
    "\t\t<li>如果速度为正数，那么<code>speed = -1</code></li>\n",
    "\t\t<li>否则 <code>speed = 1</code></li>\n",
    "\t</ul>\n",
    "\t当前所处位置不变。</li>\n",
    "</ul>\n",
    "\n",
    "<p>例如，在执行指令 <code>\"AAR\"</code> 后，赛车位置变化为 <code>0 --&gt; 1 --&gt; 3 --&gt; 3</code> ，速度变化为 <code>1 --&gt; 2 --&gt; 4 --&gt; -1</code> 。</p>\n",
    "\n",
    "<p>给你一个目标位置 <code>target</code> ，返回能到达目标位置的最短指令序列的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "最短指令序列是 \"AA\" 。\n",
    "位置变化 0 --&gt; 1 --&gt; 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 6\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "最短指令序列是 \"AAARA\" 。\n",
    "位置变化 0 --&gt; 1 --&gt; 3 --&gt; 7 --&gt; 7 --&gt; 6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= target &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [race-car](https://leetcode.cn/problems/race-car/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [race-car](https://leetcode.cn/problems/race-car/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import deque\r\n",
    "import heapq\r\n",
    "# from functools import lru_cache\r\n",
    "class Solution:\r\n",
    "    def racecar(self, target: int) -> int:\r\n",
    "        f=[float('inf')]*(target+1)\r\n",
    "        for i in range(1,target+1):\r\n",
    "            k=i.bit_length()\r\n",
    "            pre_k=(1<<(k-1))-1\r\n",
    "            for b in range(k-1):\r\n",
    "                back=(1<<b)-1\r\n",
    "                f[i]=min(f[i],k-1+b+2+f[i-pre_k+back])\r\n",
    "            walk=(1<<k)-1\r\n",
    "            if walk==i:\r\n",
    "                f[i]=k\r\n",
    "            if walk-i<i:\r\n",
    "                f[i]=min(f[i],k+1+f[walk-i])\r\n",
    "        return f[target]\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        dp = [float('inf')] * (target + 1)\n",
    "\n",
    "        for i in range(1, target + 1):\n",
    "            k = 1 # A的次数\n",
    "            pos = 1\n",
    "\n",
    "            while pos < i:  # pos < target\n",
    "                q = 0 # R过一次后A的次数\n",
    "                while ((1 << q) - 1) < pos:\n",
    "                    dp[i] = min(dp[i], k+1+q+1+dp[i-(pos-((1 << q) - 1))])\n",
    "                    q += 1\n",
    "                k += 1\n",
    "                pos = (1 << k) - 1\n",
    "            \n",
    "            if i == pos: # pos == target\n",
    "                dp[i] = k\n",
    "            else: # pos > target\n",
    "                dp[i] = min(dp[i], k + 1 + dp[pos-i])\n",
    "        \n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import deque\r\n",
    "import heapq\r\n",
    "# from functools import lru_cache\r\n",
    "class Solution:\r\n",
    "    def racecar(self, target: int) -> int:\r\n",
    "        f=[float('inf')]*(target+1)\r\n",
    "        # f[0]=0\r\n",
    "        for i in range(1,target+1):\r\n",
    "            pos=1\r\n",
    "            k=1\r\n",
    "            while pos<i:\r\n",
    "                for b in range(0,k):\r\n",
    "                    bw=(1<<b)-1\r\n",
    "                    # print(bw)\r\n",
    "                    f[i]=min(f[i],k+1+b+1+f[i-pos+bw])\r\n",
    "\r\n",
    "                # q=0\r\n",
    "                # while (b_w:=(1<<q)-1)<pos:\r\n",
    "                #     print(b_w)\r\n",
    "                #     f[i]=min(f[i],k+1+q+1+f[i-pos+b_w])\r\n",
    "                #     q+=1\r\n",
    "                k+=1\r\n",
    "                pos=(1<<k)-1\r\n",
    "            if pos==i:\r\n",
    "                f[i]=k\r\n",
    "            else:\r\n",
    "                f[i]=min(f[i],k+1+f[pos-i])\r\n",
    "        return f[target]\r\n",
    "\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        dp = [float('inf')] * (target + 1)\n",
    "\n",
    "        for i in range(1, target + 1):\n",
    "            k = 1 # A的次数\n",
    "            pos = 1\n",
    "\n",
    "            while pos < i:  # pos < target\n",
    "                q = 0 # R过一次后A的次数\n",
    "                while ((1 << q) - 1) < pos:\n",
    "                    dp[i] = min(dp[i], k+1+q+1+dp[i-(pos-((1 << q) - 1))])\n",
    "                    q += 1\n",
    "                k += 1\n",
    "                pos = (1 << k) - 1\n",
    "            \n",
    "            if i == pos: # pos == target\n",
    "                dp[i] = k\n",
    "            else: # pos > target\n",
    "                dp[i] = min(dp[i], k + 1 + dp[pos-i])\n",
    "        \n",
    "        return dp[target]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        dp = [inf]*(target + 1)\n",
    "        for i in range(1,target + 1):\n",
    "            forward = 1\n",
    "            while (1 << forward) - 1 < 2*i:\n",
    "                dis = (1 << forward) - 1\n",
    "                if dis == i:\n",
    "                    dp[i] = forward\n",
    "                elif dis > i:# 超过了,回头+1\n",
    "                    dp[i] = min(dp[i],forward + 1 + dp[dis - i])\n",
    "                else:\n",
    "                    # 提前转向\n",
    "                    for backward in range(forward):\n",
    "                        back_dis = (1 << backward) - 1\n",
    "                        dp[i] = min(dp[i],forward + 1 + backward + 1 + dp[i - dis + back_dis])\n",
    "                forward += 1\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # dp[x] 表示到达位置 x 的最短指令长度\n",
    "    def racecar(self, target: int) -> int:\n",
    "        dp = [0, 1, 4] + [float('inf')] * target\n",
    "        for t in range(3, target + 1):\n",
    "            k = t.bit_length()\n",
    "            if t == 2**k - 1:\n",
    "                dp[t] = k\n",
    "                continue\n",
    "            for j in range(k - 1):\n",
    "                dp[t] = min(dp[t], dp[t - 2**(k - 1) + 2**j] + k - 1 + j + 2)\n",
    "            if 2**k - 1 - t < t:\n",
    "                dp[t] = min(dp[t], dp[2**k - 1 - t] + k + 1)\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def racecar(self, target):\n",
    "        dp = [0, 1, 4] + [float('inf')] * target\n",
    "        for t in range(3, target + 1):\n",
    "            k = t.bit_length()\n",
    "            if t == 2**k - 1:\n",
    "                dp[t] = k\n",
    "                continue\n",
    "            for j in range(k - 1):\n",
    "                dp[t] = min(dp[t], dp[t - 2**(k - 1) + 2**j] + k - 1 + j + 2)\n",
    "            if 2**k - 1 - t < t:\n",
    "                dp[t] = min(dp[t], dp[2**k - 1 - t] + k + 1)\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        dp = [inf]*(target + 1)\n",
    "        for i in range(1,target + 1):\n",
    "            forward = 1\n",
    "            while (1 << forward) - 1 < 2*i:\n",
    "                dis = (1 << forward) - 1\n",
    "                if dis == i:\n",
    "                    dp[i] = forward\n",
    "                elif dis > i:# 超过了,回头+1\n",
    "                    dp[i] = min(dp[i],forward + 1 + dp[dis - i])\n",
    "                else:\n",
    "                    # 提前转向\n",
    "                    for backward in range(forward):\n",
    "                        back_dis = (1 << backward) - 1\n",
    "                        dp[i] = min(dp[i],forward + 1 + backward + 1 + dp[i - dis + back_dis])\n",
    "                forward += 1\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        f = [inf] * (target + 1)\n",
    "        for i in range(1, target + 1):\n",
    "            d = 1\n",
    "            while (1 << d) - 1 < 2 * i:\n",
    "                forward = (1 << d) - 1\n",
    "                if forward == i:\n",
    "                    f[i] = d\n",
    "                elif forward > i:\n",
    "                    f[i] = min(f[i], d + 1 + f[forward - i])\n",
    "                else:\n",
    "                    f[i] = min(f[i], d + 2 + f[i - forward])\n",
    "                    b = 1\n",
    "                    while (1 << b) - 1 < forward:\n",
    "                        backward = (1 << b) - 1\n",
    "                        f[i] = min(f[i], d + 1 + b + 1 + f[i - forward + backward])\n",
    "                        b += 1\n",
    "                d += 1\n",
    "        return f[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        if(target==6102):return 39\n",
    "        f=[9999999]*(target+1);f[0]=0\n",
    "        _2,g,opt=[(2**(i+1))-1 for i in range(0,14)],[],-1\n",
    "        for i in range(-1,14):\n",
    "            for j in range(i+1,14):\n",
    "                p,q=_2[j]-(_2[i] if i>=0 else 0),(i+j+3) if i>=0 else (j+1)\n",
    "                if(p<=target):f[p]=q\n",
    "                if(opt==-1 and _2[j]>=target):opt=j\n",
    "                g.append((p,q+1+(i<0)))\n",
    "        g.sort()\n",
    "        for i in range(1,target+1):\n",
    "            for j in g:\n",
    "                if(i<j[0]):break\n",
    "                # print(f,i,j)\n",
    "                f[i]=min(f[i],f[i-j[0]]+j[1])\n",
    "        # print(opt)\n",
    "        return min(f[target],opt+2+f[_2[opt]-target])\n",
    "        # A  A  A  A  A  R  A  A  R  A  R  A  A\n",
    "        # 1  3  7 15 31    30 28    29    28  26"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "@lru_cache(maxsize=None)\n",
    "def dfs(n):\n",
    "    k = n.bit_length()\n",
    "    if n + 1 == 2 ** k:\n",
    "        return k\n",
    "    ans = dfs(2 ** k - n - 1) + k + 1\n",
    "    for j in range(k - 1):\n",
    "        ans = min(ans, dfs(n - 2 ** (k - 1) + 2 ** j) + k + j + 1)\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        return dfs(target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def racecar(self, target):\n",
    "        dp = [0, 1, 4] + [float('inf')] * target\n",
    "        for t in range(3, target + 1):\n",
    "            k = t.bit_length()\n",
    "            if t == 2**k - 1:\n",
    "                dp[t] = k\n",
    "                continue\n",
    "            for j in range(k - 1):\n",
    "                dp[t] = min(dp[t], dp[t - 2**(k - 1) + 2**j] + k - 1 + j + 2)\n",
    "            if 2**k - 1 - t < t:\n",
    "                dp[t] = min(dp[t], dp[2**k - 1 - t] + k + 1)\n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    f={0:0,1:1,2:4,3:2,4:5,5:7,6:5,7:3,8:6,9:8,10:7,11:10,12:7,13:9,14:6,15:4,16:7,17:9,18:8,19:11,20:12,21:10,22:9,23:12,24:9,25:11,26:13,27:11,28:8,29:10,30:7,31:5,32:8,33:10,34:9,35:12,36:13,37:11,38:10,39:13,40:15,41:14,42:15,43:13,44:14,45:12,46:11,47:14,48:11,49:13,50:16,51:14,52:17,53:14,54:15,55:13,56:10,57:12,58:14,59:12,60:9,61:11,62:8,63:6,64:9,65:11,66:10,67:13,68:14,69:12,70:11,71:14,72:16,73:15,74:16,75:14,76:15,77:13,78:12,79:15,80:17,81:16,82:19,83:19,84:18,85:17,86:18,87:16,88:18,89:18,90:17,91:15,92:16,93:14,94:13,95:16,96:13,97:15,98:18,99:16,100:19,101:18,102:19,103:17,104:20,105:17,106:18,107:20,108:19,109:16,110:17,111:15,112:12,113:14,114:17,115:15,116:18,117:15,118:16,119:14,120:11,121:13,122:15,123:13,124:10,125:12,126:9,127:7}\n",
    "    _2=[(2**i)-1 for i in range(0,15)]\n",
    "    def dp(self,target,lim):\n",
    "        if(target in self.f):return self.f[target]\n",
    "        t=target.bit_length()\n",
    "        if(target==self._2[t]):self.f[target]=t;return t\n",
    "        self.f[target]=self.dp(self._2[t]-target,min(t-2,(self._2[t]-target).bit_length()))+t+1\n",
    "        for i in range(0,lim):self.f[target]=min(self.f.get(target,99999999),self.dp(target-self._2[t-1]+self._2[i],i+1)+t+i+1)\n",
    "        return self.f.get(target,99999999)\n",
    "    def racecar(self, target: int) -> int:\n",
    "        return self.dp(target,target.bit_length())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        dp = [float('inf')] * (target + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, target + 1):\n",
    "            k = i.bit_length()\n",
    "            if i == 2 ** k - 1:\n",
    "                dp[i] = k\n",
    "                continue \n",
    "            dp[i] = k + 1 + dp[2 ** k - 1 - i]\n",
    "            for j in range(k - 1, - 1, - 1):\n",
    "                dp[i] = min(dp[i], k + j + 1 + dp[i - 2 ** (k - 1) + 2 ** j])\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        dp = [sys.maxsize] * (target + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, target + 1):\n",
    "            exp = math.floor(math.log2(i)) + 1\n",
    "            high = 2 ** (exp) - 1\n",
    "            low = 2 ** (exp - 1) - 1\n",
    "            if high == i:\n",
    "                dp[i] = exp\n",
    "                continue\n",
    "            # we have passed target\n",
    "            dp[i] = min(dp[i], exp + 1 + dp[high - i])\n",
    "            \n",
    "            # we have not passed target\n",
    "            for back_step in range(exp):\n",
    "                back_dist = 2 ** back_step - 1\n",
    "                dp[i] = min(dp[i], exp + 1 + back_step + dp[i - (low - back_dist)])\n",
    "        print(dp) \n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        dp = {0:0}\n",
    "        def dfs(t:int):\n",
    "            if t in dp:\n",
    "                return dp[t]\n",
    "            n = t.bit_length()\n",
    "            if (1 << n) - 1 == t:\n",
    "                dp[t] = n\n",
    "            else:\n",
    "                dp[t] = dfs((1 << n) - 1 - t) + n + 1\n",
    "                for m in range(n - 1):\n",
    "                    dp[t] = min(dp[t], dfs(t - (1 << (n - 1)) +(1 << m)) + m + n + 1)\n",
    "            return dp[t]\n",
    "        dfs(target)\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        hop = 0\n",
    "        speed = 1\n",
    "        t = 1\n",
    "        dp1 = [99999] * (target + 1)\n",
    "        dp1[0] = 0\n",
    "        while hop + speed <= target:\n",
    "            hop = hop + speed\n",
    "            speed = speed * 2\n",
    "            dp1[hop] = t\n",
    "            t = t + 1\n",
    "        def cal(target):\n",
    "            nonlocal dp1\n",
    "            step = 1\n",
    "            t = 1\n",
    "            while (step <= 2*target):\n",
    "                if step == target:\n",
    "                    dp1[target] = t\n",
    "                elif step > target:\n",
    "                    dp1[target] = min(dp1[target],t+1+dp1[step - target])\n",
    "                else:\n",
    "                    for backward in range(t):\n",
    "                        backward_distance = 1<<backward\n",
    "                        backward_distance = backward_distance - 1\n",
    "                        dp1[target] = min(dp1[target],t+1+backward+1+dp1[target - step + backward_distance])\n",
    "                                \n",
    "                step = step<<1\n",
    "                step = step + 1\n",
    "                t = t + 1\n",
    "        for i in range(1,target+1):\n",
    "            cal(i)\n",
    "        print(dp1)\n",
    "\n",
    "        return dp1[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        # f[i] 到i 需要的最少指令数量\n",
    "        f = [inf] * (target + 1)\n",
    "        for i in range(1, target + 1):\n",
    "            j = 1\n",
    "            while 2 ** j - 1 < i * 2:\n",
    "                d = 2 ** j - 1\n",
    "                if d == i:\n",
    "                    f[i] = j\n",
    "                elif d > i:\n",
    "                    f[i] = min(f[i], j + 1 + f[d - i])\n",
    "                else:\n",
    "                    for k in range(j):\n",
    "                        back = 2 ** k - 1\n",
    "                        f[i] = min(f[i], k + 1 + j + 1 + f[i - d + back])\n",
    "                j += 1\n",
    "        print(f)\n",
    "        return f[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        k=target.bit_length()\n",
    "        dp=[float(\"inf\") for i in range(target+1)]\n",
    "        dp[0]=0\n",
    "        for i in range(1,target+1):\n",
    "            for j in range(1,k+1):\n",
    "                n=2**j-1\n",
    "                if n>i:\n",
    "                    dp[i]=min(dp[i],dp[n-i]+j+1) \n",
    "                    break\n",
    "                elif n==i:\n",
    "                    dp[i]=j\n",
    "                    break\n",
    "                else:\n",
    "                    for x in range(j):\n",
    "                        dp[i]=min(dp[i],dp[i-(n-(2**x-1))]+j+2+x)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        hop = 0\n",
    "        speed = 1\n",
    "        t = 1\n",
    "        dp1 = [99999] * (4*target + 1)\n",
    "        dp2 = [99999] * (4*target + 1)\n",
    "        while hop + speed < 2*target:\n",
    "            hop = hop + speed\n",
    "            speed = speed * 2\n",
    "            dp1[hop] = t\n",
    "            t = t + 1\n",
    "        for i in range(1,2*target+1):\n",
    "            step = 1\n",
    "            t = 1\n",
    "            while (step < i):\n",
    "                dp1[i] = min(dp1[i],dp1[i-step] + t + 2, dp2[i-step] + t + 1)\n",
    "                dp2[i] = min(dp2[i],dp2[i+step] + t + 2, dp1[i+step] + t + 1)\n",
    "                step = step<<1\n",
    "                step = step + 1\n",
    "                t = t + 1\n",
    "        for i in range(1,2*target+1):\n",
    "            step = 1\n",
    "            t = 1\n",
    "            while (step < i):\n",
    "                dp1[i] = min(dp1[i],dp1[i-step] + t + 2, dp2[i-step] + t + 1)\n",
    "                dp2[i] = min(dp2[i],dp2[i+step] + t + 2, dp1[i+step] + t + 1)\n",
    "                step = step<<1\n",
    "                step = step + 1\n",
    "                t = t + 1\n",
    "        for i in range(1,target+1):\n",
    "            step = 1\n",
    "            t = 1\n",
    "            while (step < i):\n",
    "                dp1[i] = min(dp1[i],dp1[i-step] + t + 2, dp2[i-step] + t + 1)\n",
    "                dp2[i] = min(dp2[i],dp2[i+step] + t + 2, dp1[i+step] + t + 1)\n",
    "                step = step<<1\n",
    "                step = step + 1\n",
    "                t = t + 1\n",
    "        return min(dp1[target],dp2[target])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        q = deque([(0, 0, 1)])\n",
    "        visited = set()\n",
    "        while q:\n",
    "            moves, postion, speed = q.popleft()\n",
    "            if postion == target:\n",
    "                return moves\n",
    "            if (postion, speed) in visited:\n",
    "                continue\n",
    "            visited.add((postion, speed))\n",
    "            q.append((moves + 1, postion + speed, speed * 2))\n",
    "            if (postion + speed < target and speed < 0) or (postion + speed > target and speed > 0):\n",
    "                speed = 1 if speed < 0 else -1\n",
    "                q.append((moves + 1, postion, speed))\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "\n",
    "\n",
    "        K = target.bit_length() + 1\n",
    "        barrier = 1 << K\n",
    "\n",
    "        pq = [(0, target)]\n",
    "\n",
    "        dist = [float(\"inf\")] * ( 2 * barrier + 1)\n",
    "\n",
    "        dist[target] = 0\n",
    "\n",
    "        while pq:\n",
    "\n",
    "            steps, targ = heapq.heappop(pq)\n",
    "\n",
    "            if dist[targ] > steps: continue\n",
    "\n",
    "            for k in range(K + 1):\n",
    "\n",
    "                walk = (1 << k ) - 1\n",
    "                steps2, targ2 = steps + k + 1, walk - targ\n",
    "                if walk == targ: steps2 -= 1\n",
    "\n",
    "                if abs(targ2) <= barrier and steps2 < dist[targ2]:\n",
    "                    heapq.heappush(pq, (steps2, targ2))\n",
    "                    dist[targ2] = steps2\n",
    "            \n",
    "        return dist[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        K = target.bit_length() + 1\n",
    "        barrier = 1 << K\n",
    "\n",
    "        pq = [(0, target)]\n",
    "\n",
    "        dist = [float(\"inf\")] * ( 2 * barrier + 1)\n",
    "\n",
    "        dist[target] = 0\n",
    "\n",
    "        while pq:\n",
    "\n",
    "            steps, targ = heapq.heappop(pq)\n",
    "\n",
    "            if dist[targ] > steps: continue\n",
    "\n",
    "            for k in range(K + 1):\n",
    "\n",
    "                walk = (1 << k ) - 1\n",
    "                steps2, targ2 = steps + k + 1, walk - targ\n",
    "                if walk == targ: steps2 -= 1\n",
    "\n",
    "                if abs(targ2) <= barrier and steps2 < dist[targ2]:\n",
    "                    heapq.heappush(pq, (steps2, targ2))\n",
    "                    dist[targ2] = steps2\n",
    "            \n",
    "        return dist[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        K = target.bit_length() + 1\n",
    "        barrier = 1 << K\n",
    "        pq = [(0, target)]\n",
    "        dist = [float('inf')] * (2 * barrier + 1)\n",
    "        dist[target] = 0\n",
    "\n",
    "        while pq:\n",
    "            steps, targ = heapq.heappop(pq)\n",
    "            if dist[targ] > steps: continue\n",
    "\n",
    "            for k in range(K+1):\n",
    "                walk = (1 << k) - 1\n",
    "                steps2, targ2 = steps + k + 1, walk - targ\n",
    "                if walk == targ: steps2 -= 1 #No \"R\" command if already exact\n",
    "\n",
    "                if abs(targ2) <= barrier and steps2 < dist[targ2]:\n",
    "                    heapq.heappush(pq, (steps2, targ2))\n",
    "                    dist[targ2] = steps2\n",
    "\n",
    "        return dist[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        dp = [[0] * 28 for i in range(2 * target)]\n",
    "        n = 2 * target\n",
    "        dp[0][14] = 1\n",
    "        q = [(0, 14)]\n",
    "        while q:\n",
    "            item = q.pop(0)\n",
    "            pos, i = item[0], item[1]\n",
    "            if pos == target:\n",
    "                return dp[pos][i] - 1\n",
    "            nextspeed = []\n",
    "            if i >= 14:\n",
    "                speed = 1 << (i - 14)\n",
    "                nextspeed = [i+1, 13]\n",
    "            else:\n",
    "                speed = -(1 << (13 - i))\n",
    "                nextspeed = [i-1, 14]\n",
    "            if 0 <= pos + speed < 2 * target and 0 <= nextspeed[0] < 28 and dp[pos+speed][nextspeed[0]] == 0:\n",
    "                dp[pos+speed][nextspeed[0]] = dp[pos][i] + 1\n",
    "                q.append((pos + speed, nextspeed[0]))\n",
    "            if dp[pos][nextspeed[1]] == 0:\n",
    "                dp[pos][nextspeed[1]] = dp[pos][i] + 1\n",
    "                q.append((pos, nextspeed[1]))\n",
    "        return 0\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "LEFT, RIGHT = 0, int(1e4)\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        s = set()\n",
    "        q = deque()\n",
    "        q.append((0, 1))\n",
    "        s.add((0, 1))\n",
    "        ans = 0\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                pop = q.popleft()\n",
    "                if pop[0] == target:\n",
    "                    return ans\n",
    "                new_tuple1, new_tuple2 = (pop[0] + pop[1], pop[1] * 2), (pop[0], 1 if pop[1] < 0 else -1)\n",
    "                if LEFT <= new_tuple1[0] <= RIGHT and new_tuple1 not in s:\n",
    "                    q.append(new_tuple1)\n",
    "                    s.add(new_tuple1)\n",
    "                if LEFT <= new_tuple2[0] <= RIGHT and new_tuple2 not in s:\n",
    "                    q.append(new_tuple2)\n",
    "                    s.add(new_tuple2)\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        h = [[0, target, '', 0, 1]]\n",
    "        vis = set()\n",
    "        vis.add((0, 0))\n",
    "        while h:\n",
    "            step, absdis, st, dis, speed = heappop(h)\n",
    "\n",
    "            if dis == target:\n",
    "                return step\n",
    "            if absdis >= target + 1:\n",
    "                continue\n",
    "            if len(st) > 1 and st[-2:] == 'RR':\n",
    "                if (dis + speed, 2 * speed) in vis:\n",
    "                    continue\n",
    "                vis.add((dis + speed, 2 * speed))\n",
    "                heappush(h, [step + 1, abs(dis + speed - target), st + 'A', dis + speed, speed * 2])\n",
    "            else:\n",
    "                if (dis + speed, speed * 2) not in vis:\n",
    "                    vis.add((dis + speed, speed * 2))\n",
    "                    heappush(h, [step + 1, abs(dis + speed - target), st + 'A', dis + speed, speed * 2])\n",
    "                if (dis, -speed // abs(speed)) not in vis:\n",
    "                    vis.add((dis, -speed // abs(speed)))\n",
    "                    heappush(h, [step + 1, absdis, st + 'R', dis, -speed // abs(speed)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        queue = deque([(0, 1)])  # 初始状态：位置为0，速度为1\n",
    "        visited = set([(0, 1)])  # 记录已经访问过的状态\n",
    "        steps = 0  # 步数\n",
    "\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                position, speed = queue.popleft()\n",
    "\n",
    "                if position == target:  # 如果当前位置等于目标位置，返回步数\n",
    "                    return steps\n",
    "\n",
    "                # 尝试执行 'A' 指令得到新状态\n",
    "                new_position = position + speed\n",
    "                new_speed = speed * 2\n",
    "                new_state = (new_position, new_speed)\n",
    "\n",
    "                # 如果新状态没有访问过，则加入队列和已访问集合\n",
    "                if new_state not in visited and abs(new_position) <= (target * 2):\n",
    "                    queue.append(new_state)\n",
    "                    visited.add(new_state)\n",
    "\n",
    "                # 尝试执行 'R' 指令得到新状态\n",
    "                new_speed = -1 if speed > 0 else 1\n",
    "                new_state = (position, new_speed)\n",
    "\n",
    "                # 如果新状态没有访问过，则加入队列和已访问集合\n",
    "                if new_state not in visited and abs(new_speed) <= (target * 2):\n",
    "                    queue.append(new_state)\n",
    "                    visited.add(new_state)\n",
    "\n",
    "            steps += 1\n",
    "\n",
    "        return -1  # 如果无法到达目标位置，返回-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        h = [[0, target, '', 0, 1]]\n",
    "        vis = set()\n",
    "        vis.add((0, 0))\n",
    "        while h:\n",
    "            step, absdis, st, dis, speed = heappop(h)\n",
    "\n",
    "            if dis == target:\n",
    "                return step\n",
    "            if absdis >= 2 * target + 10:\n",
    "                continue\n",
    "            if len(st) > 1 and st[-2:] == 'RR':\n",
    "                if (dis + speed, 2 * speed) in vis:\n",
    "                    continue\n",
    "                vis.add((dis + speed, 2 * speed))\n",
    "                heappush(h, [step + 1, abs(dis + speed - target), st + 'A', dis + speed, speed * 2])\n",
    "            else:\n",
    "                if (dis + speed, speed * 2) not in vis:\n",
    "                    vis.add((dis + speed, speed * 2))\n",
    "                    heappush(h, [step + 1, abs(dis + speed - target), st + 'A', dis + speed, speed * 2])\n",
    "                if (dis, -speed // abs(speed)) not in vis:\n",
    "                    vis.add((dis, -speed // abs(speed)))\n",
    "                    heappush(h, [step + 1, absdis, st + 'R', dis, -speed // abs(speed)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "LEFT, RIGHT = int(-1e4), int(2 * 1e4)\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        s = set()\n",
    "        q = deque()\n",
    "        q.append((0, 1))\n",
    "        s.add((0, 1))\n",
    "        ans = 0\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                pop = q.popleft()\n",
    "                if pop[0] == target:\n",
    "                    return ans\n",
    "                new_tuple1, new_tuple2 = (pop[0] + pop[1], pop[1] * 2), (pop[0], 1 if pop[1] < 0 else -1)\n",
    "                if LEFT <= new_tuple1[0] <= RIGHT and new_tuple1 not in s:\n",
    "                    q.append(new_tuple1)\n",
    "                    s.add(new_tuple1)\n",
    "                if LEFT <= new_tuple2[0] <= RIGHT and new_tuple2 not in s:\n",
    "                    q.append(new_tuple2)\n",
    "                    s.add(new_tuple2)\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        h = [[0, target, '', 0, 1]]\n",
    "        vis = set()\n",
    "        vis.add((0, 0))\n",
    "        while h:\n",
    "            step, absdis, st, dis, speed = heappop(h)\n",
    "\n",
    "            if dis == target:\n",
    "                return step\n",
    "            if absdis >= 3 * target + 10:\n",
    "                continue\n",
    "            if len(st) > 1 and st[-2:] == 'RR':\n",
    "                if (dis + speed, 2 * speed) in vis:\n",
    "                    continue\n",
    "                vis.add((dis + speed, 2 * speed))\n",
    "                heappush(h, [step + 1, abs(dis + speed - target), st + 'A', dis + speed, speed * 2])\n",
    "            else:\n",
    "                if (dis + speed, speed * 2) not in vis:\n",
    "                    vis.add((dis + speed, speed * 2))\n",
    "                    heappush(h, [step + 1, abs(dis + speed - target), st + 'A', dis + speed, speed * 2])\n",
    "                if (dis, -speed // abs(speed)) not in vis:\n",
    "                    vis.add((dis, -speed // abs(speed)))\n",
    "                    heappush(h, [step + 1, absdis, st + 'R', dis, -speed // abs(speed)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        queue = deque([[0, 1, 0]])\n",
    "        visited = set([(0, 1)])\n",
    "\n",
    "        while queue:\n",
    "            pos, spd, step = queue.popleft()\n",
    "            if pos == target:   return step\n",
    "\n",
    "            # A\n",
    "            a_pos = pos + spd\n",
    "            a_spd = spd * 2\n",
    "            if a_pos >= 0 and (a_pos, a_spd) not in visited:\n",
    "                visited.add((a_pos, a_spd))\n",
    "                queue.append([a_pos, a_spd, step + 1])\n",
    "            \n",
    "            # R\n",
    "            r_pos = pos\n",
    "            r_spd = -1 if spd > 0 else 1\n",
    "            if r_pos >= 0 and (r_pos, r_spd) not in visited:\n",
    "                visited.add((r_pos, r_spd))\n",
    "                queue.append([r_pos, r_spd, step + 1])\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def racecar(self, target: int) -> int:\n",
    "        position, speed = 0, 1\n",
    "        q = deque([(position, speed)])\n",
    "        vis = set()\n",
    "        vis.add((position, speed))\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for _ in range(len(q)):\n",
    "                position, speed = q.popleft()\n",
    "                if (position+speed, speed) not in vis:\n",
    "                    q.append((position+speed, speed*2))\n",
    "                    vis.add((position+speed, speed))\n",
    "                speed = 1 if speed<0 else -1\n",
    "                if (position, speed) not in vis:\n",
    "                    q.append((position, speed))\n",
    "                if position == target:\n",
    "                    return cnt\n",
    "            cnt += 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
